import java.util.Arrays;
import java.util.Date;

/**
 * 介绍常用的数组排序方法：冒泡排序或选择排序，让学员至少掌握一种数组排序的方法。
 * 
 * @author tony.tang
 * @company www.tarena.com.cn
 * 
 */
public class Sort {

	/**
	 * 冒泡排序
	 * 
	 * @param array
	 */
	public static void bubbleSort(int[] array) {
		for (int i = 0; i < array.length - 1; ++i) { 		// 外层循环
			for (int j = 0; j < array.length - i - 1; ++j) {// 内层循环
				if (array[j] > array[j + 1]) { 				// 前一个数小于后一个数
					int temp = array[j]; 					// 将前一个数拿到旁边
					array[j] = array[j + 1]; 				// 将后面的数放到刚才的位置
					array[j + 1] = temp; 					// 在将刚才大的数放在现在的位置,也就是后面的位置
				}
			}
		}
	}

	/**
	 * 选择排序
	 * 
	 * @param array
	 */
	public static void selectionSort(int[] array) {
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = i + 1; j < array.length; j++) {
				if (array[i] > array[j]) {
					int temp = array[i];
					array[i] = array[j];
					array[j] = temp;
				}
			}
		}
	}

	/**
	 * 插入排序
	 * 
	 * @param array
	 */
	public static void insertSort(int[] array) {
		int i, j, k;
		for (i = 0; i < array.length; i++) {
			k = array[i];
			for (j = i - 1; j >= 0 && array[j] > k; j--) {
				array[j + 1] = array[j];
			}
			array[j + 1] = k;
		}
	}

	public static void main(String[] args) {
		int[] arr = new int[50000];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) (Math.random() * 1000000);
		}

		Date d1 = new Date();
		insertSort(arr);
		Arrays.sort(arr);
		Date d2 = new Date();
		long seconds = d2.getTime() - d1.getTime();

		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + ",");
			if ((i + 1) % 20 == 0) {
				System.out.println();
			}
		}
		System.out.println("\n排序花费时间：" + seconds + "毫秒");

	}

}